package ch03;

import java.util.LinkedList;
import java.util.Queue;

public class RedBlackBST<Key extends Comparable<Key>, Value> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private Node root;


    private class Node {
        Key key;
        Value value;
        int N;
        Node left, right;
        boolean color;

        public Node() {
        }

        public Node(Key key, Value value, int n, Node left, Node right, boolean color) {
            this.key = key;
            this.value = value;
            N = n;
            this.left = left;
            this.right = right;
            this.color = color;
        }
    }


    private boolean isRed(Node x) {
        if (x == null) {
            return false;
        }
        return x.color == RED;
    }

    private int size(Node x) {
        if (x == null) return 0;
        return x.N;
    }

    //左旋转
    /*
     * 1.节点旋转
     * 2.颜色切换
     * 根节点颜色不变
     * 3.数量更新
     * 子节点变父节点，新父节点旗下的子节点数不变
     * */
    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = size(h.left) + size(h.right) + 1;
        return x;

    }

    //右旋转
    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = size(h.left) + size(h.right) + 1;

        return x;

    }

    private void flipColor(Node x) {
        x.left.color = BLACK;
        x.right.color = BLACK;
        x.color = RED;

    }

    private Node put(Node h, Key key, Value value) {
        if (h == null) {
            return new Node(key, value, 1, null, null, BLACK);
        }
        int cmp = key.compareTo(h.key);

        if (cmp < 0) {
            h.left = put(h.left, key, value);

        } else if (cmp > 0) {
            h.right = put(h.right, key, value);
        } else {

            h.value = value;
        }
        if (isRed(h.right) && !isRed(h.left)) {
            h = rotateLeft(h);
        }

        if (isRed(h.left) && isRed(h.left.left)) {
            h = rotateRight(h);
        }


        if (isRed(h.left) && isRed(h.right)) {
            flipColor(h);
        }
        h.N = size(h.left) + size(h.right) + 1;

        return h;

    }

    public void put(Key key, Value value) {
        root = put(root, key, value);
        root.color = BLACK;
    }

    private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
        if (x == null) {
            return;
        }
        int cmplo = lo.compareTo(x.key);
        int cmphi = hi.compareTo(x.key);
        if (cmplo < 0) {
            keys(x.left, queue, lo, hi);
        }
        if (cmplo <= 0 && cmphi >= 0) {
            queue.add(x.key);
        }

        if (cmphi > 0) {
            keys(x.right, queue, lo, hi);
        }


    }

    public void keys(Queue<Key> queue, Key lo, Key hi) {
        keys(root, queue, lo, hi);

    }

    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(Node x, Key key) {
        if (x == null)
            return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return get(x.left, key);
        } else if (cmp > 0) {
            return get(x.right, key);
        } else
            return x.value;
    }

    public void delete(Key key) {
        root = delete(root, key);
    }


    private Node delete(Node x, Key key) {
        if (x == null) {
            return null;
        }
        int cmp = x.key.compareTo(key);
        if (cmp < 0) {
            x.left = delete(x.left, key);
        } else if (cmp > 0) {
            x.right = delete(x.right, key);

        } else {
            //组合1：被删节点无子节点，且被删结点为红色
            if (x.left == null && x.right == null && x.color == RED) {
                return null;
            }//组合4：被删结点有一个子结点，且被删结点为黑色
            else if (x.color == BLACK && x.left != null && x.right == null) {
                return x.left;
            } else if (x.color == BLACK && x.right != null && x.left == null) {
                return x.right;
            } else if (x.left != null && x.right != null) {

                Node t = x.right;
                while (t.left != null) {
                    t = t.left;
                }
                x.key = t.key;
                x.value = t.value;

                x.right = delete(x.right, t.key);
                return x;

            }
            return x;

        }
        if (x.left.key.compareTo(key) == 0) {

            if (x.right.color == BLACK) {
                Node t = x.right;
                //情形二：brother为黑色，且brother有一个与其方向不一致的红色子结点son
                if (t.left.color == RED) {
                    t.right = t.left;
                    t.left = null;

                }
                //情形一：brother为黑色，且brother有一个与其方向一致的红色子结点son
                if (t.right.color == RED) {
                    x.left = t;
                    x.left.right = null;
                    t = t.right;
                }

            } else if (x.color == RED) {
                x.color = BLACK;
                x.left = null;
                x.right.color = RED;
            } else if (x.color == BLACK && x.right.color == BLACK) {
                x.right.color = RED;
            } else if (x.color == BLACK) {
                x.left = null;
                rotateLeft(x);
            }
            //删除的节点在右边还没写
        } else if (x.right.key.compareTo(key) == 0) {
            if (x.left.color == BLACK) {
                Node t = x.left;
                if (t.right.color == RED) {
                    t.left = t.right;
                    t.right = null;
                }
                if (t.left.color == RED) {
                    x.right = t;
                    x.right.left = null;
                    t = t.left;
                }
            }
        }
        return x;
    }


    public static void main(String[] args) {
        RedBlackBST<Integer, String> redBlackBST = new RedBlackBST<>();
        redBlackBST.put(7, "sb");
        redBlackBST.put(2, "nmlgb");
        redBlackBST.put(1, "qnm");
        redBlackBST.put(6, "lszdnb");
        redBlackBST.put(3, "pa");
        Queue<Integer> queue = new LinkedList<>();
        redBlackBST.keys(queue, 1, 12);
        redBlackBST.delete(7);
        redBlackBST.keys(queue, 1, 12);

        for (Integer integer : queue) {

            System.out.println(integer + " " + redBlackBST.get(integer));
        }

    }
}
